# 两数相加： https://leetcode-cn.com/problems/add-two-numbers/

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """ 
            对于链表的问题，一定要习惯性的设立头结点！ 虽然这道题设立头结点只是方便对结果链表增加元素
            1. 头结点可以使首元结点像其他节点一样去处理，不需要特殊处理 
            2. 头结点可以保证 空链表判断的一致性。 都是L.next == None
        """
        node1, node2 = ListNode(), ListNode()
        # 设立头结点
        node1.next = l1; node2.next = l2
        # 当前元素指针，默认指向头结点
        cur1 = node1; cur2 = node2
        # 目标链表存储结果
        head = ListNode()
        p = head
        # 进位
        carry = 0
        # 当任意链表下一节点不为 None
        while cur1.next or cur2.next:
            dig1 = cur1.next.val if cur1.next else 0
            dig2 = cur2.next.val if cur2.next else 0
            # 更新指针
            if cur1.next: cur1 = cur1.next 
            if cur2.next: cur2 = cur2.next 

            # 计算和， 计算进位
            sum = dig1 + dig2 + carry
            carry = sum // 10
            # 加入结果链表
            p.next = ListNode(sum % 10)
            p = p.next

        # 如果进位不为0，那么还要加上进位
        if carry != 0: p.next = ListNode(carry)

        # 不返回头结点
        return head.next






